package com.webxiaohua.algorithm.linkedlist;

/**
 * 单链表逆序
 */
public class ReverseLinkedList {
    /**
     * @param node
     * @return
     * @desc 生成链表
     */
    public static void generateNode(Node node){
        if(node.id<5){
            node.next = new Node(node.id + 1);
            generateNode(node.next);
        }
    }

    /**
     * 递归法
     * @param head
     */
    public static Node reverseNode(Node head){
        //如果链表为空或只有一个元素直接返回
        if (head == null || head.getNext() == null) {  //当链表只有一个头节点或者只有一个结点，逆序还是原来的链表，所以直接返回
            return head;
        } else {
            Node p = head.getNext();
            Node q = head.getNext().getNext();
            p.setNext(null);//将第一个结点的next置为空，否则会出现一个环
            Node temp = null;
            while (q != null) {
                temp = q.getNext();
                q.setNext(p);
                p = q;
                q = temp;
            }
            if (q == null) {
                head.setNext(p);
                q = null;
            }
        }
        return head;
    }

    public static void main(String... args){
        Node node = new Node(0);
        generateNode(node);
        Node sortNode = node;
        System.out.println("顺序链表：");
        while(sortNode.next!=null){
            System.out.println(sortNode.id);
            sortNode = sortNode.next;
        }
        Node reverseNode = reverseNode(node);
        System.out.println("逆序链表：");
        while(reverseNode.next!=null){
            System.out.println(reverseNode.id);
            reverseNode = reverseNode.next;
        }

    }
}
